<!DOCTYPE html>
<html>
<head>
  <title>二叉树可视化示例</title>
  <style>
    #canvas {
      border: 1px solid black;
    }
  </style>
</head>
<body>
  <h1>二叉树可视化示例</h1>

  <label for="inputSequence">输入序列:</label>
  <input type="text" id="inputSequence" placeholder="输入数字序列，以空格分隔">
  <button onclick="createBinaryTree()">创建二叉树</button>

  <canvas id="canvas" width="800" height="400"></canvas>

  <script>
    // 获取 Canvas 元素
    const canvas = document.getElementById("canvas");
    const context = canvas.getContext("2d");

    class TreeNode {
      constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
      }
    }

    class BinaryTree {
      constructor() {
        this.root = null;
      }

      insert(value) {
        const newNode = new TreeNode(value);
        if (this.root === null) {
          this.root = newNode;
        } else {
          this.insertNode(this.root, newNode);
        }
        this.draw();
      }

      insertNode(node, newNode) {
        if (newNode.value < node.value) {
          if (node.left === null) {
            node.left = newNode;
          } else {
            this.insertNode(node.left, newNode);
          }
        } else {
          if (node.right === null) {
            node.right = newNode;
          } else {
            this.insertNode(node.right, newNode);
          }
        }
      }

      // 先序遍历
      preorderTraversal(node, callback) {
        if (node !== null) {
          callback(node.value);
          this.preorderTraversal(node.left, callback);
          this.preorderTraversal(node.right, callback);
        }
      }

      // 绘制二叉树
      draw() {
        context.clearRect(0, 0, canvas.width, canvas.height);
        const treeHeight = this.getHeight(this.root);
        const startX = canvas.width / 2;
        const startY = 40;
        const levelHeight = (canvas.height - 80) / (treeHeight + 1);
        this.drawNode(this.root, startX, startY, startX, levelHeight);
      }

      // 递归绘制节点和连接线
      drawNode(node, x, y, parentX, levelHeight) {
        if (node !== null) {
          // 绘制节点
          context.strokeStyle = "black";
          context.fillStyle = "white";
          context.lineWidth = 2;
          context.beginPath();
          context.arc(x, y, 20, 0, 2 * Math.PI);
          context.fill();
          context.stroke();

          // 绘制节点值
          context.fillStyle = "black";
          context.font = "16px Arial";
          context.textAlign = "center";
          context.fillText(node.value, x, y + 6);

          // 绘制连接线
          if (parentX !== null) {
            context.beginPath();
            context.moveTo(parentX, y - 20);
            context.lineTo(x, y - levelHeight + 20);
            context.stroke();
          }

          // 绘制子节点
          const childXOffset = (canvas.width /  2) / 2;
          const childY = y + levelHeight;

          this.drawNode(node.left, x - childXOffset, childY, x, levelHeight);
          this.drawNode(node.right, x + childXOffset, childY, x, levelHeight);
        }
      }

      // 获取树的高度
      getHeight(node) {
        if (node === null) {
          return 0;
        }
        const leftHeight = this.getHeight(node.left);
        const rightHeight = this.getHeight(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
      }
    }

    // 获取输入序列的值
    function getInputSequence() {
      const inputSequence = document.getElementById("inputSequence").value;
      const sequenceArray = inputSequence.split(" ").map(Number);
      return sequenceArray;
    }

    // 创建二叉树
    function createBinaryTree() {
      const sequenceArray = getInputSequence();
      const binaryTree = new BinaryTree();
      sequenceArray.forEach(value => binaryTree.insert(value));
    }
  </script>
</body>
</html>
